Most of the traditional discrete-time signal processing techniques have evolved directly from processing and filtering analog signals, and thus have been constrained by several common assumptions, like sampling and processing only regularly organized data. The field of video compression is based on basically the same assumptions, but only generalized to multi-dimensional signals.
A graph is a useful type of data representation for describing a geometrical structure of data in various application fields. Signal processing based on graph representations can generalize concepts like sampling, filtering, Fourier transforms, etc., using graphs where each signal sample represents a vertex, and signal relationships are represented by graph edges with positive weights. This disconnects the signal from its acquisition process, so that properties like sampling rate and sequences can be replaced by the properties of graph. Accordingly, more efficient signal processing method based on graph is required in many application fields as well as in the field of video compression.